1. Field of the Invention
The present invention concerns a technique for resolving defects occurring in a fast fourier transformation (FFT) network, and more particularly, to a technique for obtaining checksum in an FFT network.
2. Description of the Related Art
Conventionally, there have been proposed time redundancy, hardware redundancy and algorithm mixing the two methods in order to resolve the defects occurring in an FFT network. The time redundancy method is to duplicate the same steps of calculating data in order to detect defects by comparing the two results. The hardware redundancy method is to duplicate the circuits for calculating data. These two methods suffer a drawback in that they require more than 200% overhead for the time or hardware. In addition, the time redundancy method makes it possible to detect a temporary error in transmission, but not a defect inherent in the circuits.
However, the method of using a specific algorithm overcomes such drawbacks by employing partly the time redundancy and partly the hardware redundancy. In this case, the algorithm is applied to the input and output lines of the network. When a package of data is outputted through an FFT network with a checksum obtained by discrete fourier transform (DFT), the output data package is subjected to another calculation procedure to obtain a checksum, which is compared with the previous checksum in order to detect defects occurring in the network. This requires a hardware overhead such as checksum calculation circuits and comparators for comparing the calculated checksums. Such overhead becomes small compared to the hardware redundancy. Moreover, the checksum calculation for the input data is achieved simultaneously during transmission through the FFT network, so that the time overhead is required only for calculating upon the checksum of the output data, thereby reducing the time overhead. This method of using an algorithm has the following drawbacks when applied to the input and output lines of the network:
Firstly, the detection of a defect is made possible only after passing all the stages of an FFT network, resulting in a considerable time delay. For example, a defect occurring in the first stage circuit can be only detected in the last stage when the checksum of the data transmitted to the last stage is obtained and compared with the previous checksum of the input data. This requires retransmission of a large amount of data, degrading the efficiency of processing data.
Secondly, the data error is continuously accumulated through the network so as to mislead the detection of a defect. Namely, the value of the input data is changed by butterfly computation whenever passing each node of the FFT network. Hence, the data error indicating the defect is subjected to alteration through each node, thus misleading the detection.
Thirdly, it is impossible to considerably reduce the overhead ratio of the hardware. The hardware overhead of an FFT network for eliminating defects is generally calculated by the number of the multipliers required in addition. According to this, there is required about 1.2 to 2/log.sub.2 N for a design to presently meet the minimum hardware overhead, where "N" represents the total number of the input data.
The following patents each disclose features in common with the present invention but do not teach or suggest the specifically recited technique for obtaining a checksum in accordance with the present invention: U.S. Pat. No. 5,481,488 to Luo et al., entitled Block Floating Point Mechanism For Fast Fourier Transform Processor, U.S. Pat. No. 5,491,652 to Luo et al., entitled Fast Fourier Transform Address Generator, U.S. Pat. No. 5,297,070 to Hua et al., entitled Transform Processing Circuit, U.S. Pat. No. 4,977,533 to Miyabayashi et al., entitled Method For Operating An FFT Processor, U.S. Pat. No. 5,091,875 to Wong et al., entitled Fast Fourier Transform (FFT) Addressing Apparatus And Method, U.S. Pat. No. 5,500,864 to Gonia et al., entitled Checksum Calculation Unit And Method For Error Detection On Data Packets, and U.S. Pat. No. 5,247,524 to Callon, entitled Method For Generating A CHecksum.